• Função:
  • Minimizar o número de pontos de acesso (Pa’s) na área de 800 x 800 metros que atendam à demanda de 475 clientes (Pd’s).
• Restrições:
  • O alcance de cada Pa é um círculo com raio de 85 metros.
  • O número de Pa’s não deve ultrapassar 100.
  • A soma da demanda dos Pd’s cobertos por um dado Pa não deve ultrapassar 150 Mbps.

• Continua:
  • Existem infinitas coordenadas de possíveis localizações para os Pa’s tornando o problema computacionalmente insolúvel.
• Discreta:
  • Considerando a área de 800 x 800 metros discretizada em inteiros, existem 640.000 possíveis localizações para os Pa’s tornando o problema computacionalmente intratável.
  • Matrizes \(M_{(i,j)}\) foram construídas para discretizar o espaço de busca com \(i, j \in \{1, 2, ..., 800 \}\).

• Espaços discretos menores que \(M_{(8,8)}\) não apresentaram solução ótima.
• Espaços maiores que \(M_{(150,150)}\) apresentaram custo computacional muito elevado.

• O algorítimo foi desenhado para escanear os espaços discretos de \(M_{(8,8)}\) até \(M_{(150,150)}\) na área de 800 x 800 com intervalos iguais entre os pontos.
• Para ilustrar, foi considerado o espaço de \(M_{(9,9)}\), que representa 81 possíveis localizações para os Pa’s.

• A cada iteração o algoritmo inspeciona cada coordenada do espaço discretizado de possíveis localizações dos Pa’s e determina o PA que cobre o maior número de Pd’s.
• Se a condição de 150 Mbps não for violada, o índice do PA com maior cobertura de Pd’s é armazenado e esses Pd’s são removidos.
• O algoritmo reinicia a busca do próximo PA que cobre mais Pd’s dentre os restantes.

• O algoritmo para quando cobre pelo menos 475 dos 500 Pd’s atendendo as restrições de consumo de banda e limite de Pa’s.

O algoritmo conta o número de Pd’s cobertos por cada uma das 81 possíveis localizações para o 1º PA e soma os Mbps demandados.

O máximo de 202 Pd’s são cobertos pelo PA nas coordenadas (200, 200).

O total de 146 Mbps de demanda desses Pd’s não viola a condição de menor que 150 Mbps.

As coordenadas deste 1º PA são armazenadas.

Os 202 Pd’s cobertos por este PA são removidos por já estarem cobertos.

O algoritmo realiza a mesma busca e contagem da primeira iteração, porém desconsiderando os Pd’s cobertos pelo 1º PA.

O máximo de 199 Pd’s são cobertos pelo PA nas coordenadas (600, 600).

O total de 141 Mbps de demanda destes Pd’s não viola a condição de menor que 150 Mbps.

Da mesma forma são armazenadas as coordenadas desse 2º PA.

Os 199 Pd’s cobertos por este PA também são removidos por já estarem cobertos.

O algoritmo para.

O resultado da busca retorna uma solução no mínimo local de 17 PA´s.

A condição de que sejam cobertos 95% ou 475 do total de 500 Pd’s é atendida.

A restrição de número de Pa’s menor que 100 é atendida.

A restrição de que a soma da demanda dos Pd’s cobertos por um Pa não exceda 150 Mbps é atendida.

As informações dos índices, número de Pd’s atendidos e total da demanda em Mbps de cada Pa podem ser recuperadas.